// 300.最长递增子序列[dp动态规划贪心二分low_bound]
// https://leetcode-cn.com/problems/longest-increasing-subsequence/
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
// 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
// 输入：nums = [0,1,0,3,2,3]
// 输出：4
// 输入：nums = [7,7,7,7,7,7,7]
// 输出：1
// 提示：1 <= nums.length <= 2500, -104 <= nums[i] <= 104
// 进阶：你能将算法的时间复杂度降低到O(n log(n)) 吗
// dp动态规划 时间 O(n^2)
// 定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意
// nums[i] 必须被选取。 我们从小到大计算 dp 数组的值，在计算 dp[i]
// 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
// dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
// 即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。
// 贪心+二分 时间 O(nlogn)
//流程：设当前已求出的最长上升子序列的长度为 nMaxIndex 初始时为1
// dp[i]表示　i之前求得的最长递增子序列比如dp={0,6,10,18,36,37,56,58,73,91},dp[0]不使用
//从前往后遍历数组 nums，在遍历到 nums[i] 时：
//如果 nums[i]>dp[nMaxIndex],则直接加入到dp数组末尾，并更新 nMaxLen=nMaxLen+1
//否则，在 dp 数组中二分查找，找到第一个比 nums[i] 小的数
// dp[k],并更新dp[k+1]=nums[i]

#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution_lowBound {
 public:
  int lengthOfLIS(vector<int> nums) {
    if (nums.size() == 0) {
      return 0;
    }
    vector<int> dp(nums.size() + 1, 0);
    size_t nMaxIndex = 1;
    dp[nMaxIndex] = nums[0];
    PF("dp.push=%d, %d\n", nMaxIndex, dp[nMaxIndex]);
    for (size_t i = 1; i < nums.size(); i++) {
      PF("\n ====n %d=======\n", nums[i]);
      if (nums[i] > dp[nMaxIndex]) {
        dp[++nMaxIndex] = nums[i];
        PF("dp.push=%d, %d\n", nMaxIndex, dp[nMaxIndex]);
      } else {
        // 最末数字比 nums[i] 大，更新 dp[]
        size_t pos2 =
            std::lower_bound(dp.begin() + 1, dp.begin() + nMaxIndex, nums[i]) -
            dp.begin();
        dp[pos2] = nums[i];
        PF("dp.mod=%d, %d\n", pos2, dp[pos2]);
      }
      for (auto d : dp) PF("%d,", d);
      PF("\n");
    }
    return nMaxIndex;
  }
};
int main() {
  vector<int> vtNum = {10, 9, 2, 5, 3, 7, 101, 18};
  for (auto n : vtNum) PF("%d,", n);
  PF("\n");
  Solution_lowBound sol;
  PF("%d\n", sol.lengthOfLIS(vtNum));
  return 0;
}

// 10,9,2,5,3,7,101,18,
// dp.push=1, 10
//  ====n 9=======
// dp.mod=1, 9
// 0,9,0,0,0,0,0,0,0,
//  ====n 2=======
// dp.mod=1, 2
// 0,2,0,0,0,0,0,0,0,
//  ====n 5=======
// dp.push=2, 5
// 0,2,5,0,0,0,0,0,0,
//  ====n 3=======
// dp.mod=2, 3
// 0,2,3,0,0,0,0,0,0,
//  ====n 7=======
// dp.push=3, 7
// 0,2,3,7,0,0,0,0,0,
//  ====n 101=======
// dp.push=4, 101
// 0,2,3,7,101,0,0,0,0,
//  ====n 18=======
// dp.mod=4, 18
// 0,2,3,7,18,0,0,0,0,
// 4
